package heap;

import java.util.PriorityQueue;

/**
 * 给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
 * 你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
 * 当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
 * 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
 * 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
 * 如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
 * <p>
 * 示例 1：
 * 输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
 * 输出：4
 * 解释：从建筑物 0 出发，你可以按此方案完成旅程：
 * - 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
 * - 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
 * - 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
 * - 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
 * 无法越过建筑物 4 ，因为没有更多砖块或梯子。
 * <p>
 * 示例 2：
 * 输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
 * 输出：7
 * <p>
 * 示例 3：
 * 输入：heights = [14,3,19,3], bricks = 17, ladders = 0
 * 输出：3
 *
 * @author Jisheng Huang
 * @version 20250529
 */
public class FurthestBuilding_1642 {
    /**
     * 尽量先用砖块，当砖块不满足的时候，用之前记录的heap去除top加到砖块，并且梯子数量减少，这样就是最优解
     *
     * @param heights the given Integer array
     * @param bricks  the given bricks
     * @param ladders the given ladders
     * @return the furthest building you can reach
     */
    public static int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
        int n = heights.length;

        // Loop through the sorted array
        for (int i = 1; i < n; ++i) {
            int diff = heights[i] - heights[i - 1];

            if (diff > 0) {
                pq.offer(diff);

                // Use bricks first
                if (bricks >= diff) {
                    bricks -= diff;
                } else if (ladders > 0) {   // When you don't have bricks, use ladders
                    bricks += pq.poll();
                    --ladders;
                    bricks -= diff;

                    if (bricks < 0) {
                        return i - 1;
                    }
                } else {    // When you have neither bricks nor ladders
                    return i - 1;
                }
            }
        }

        return n - 1;
    }

    public static void main(String[] args) {
        int[] heights = {4, 2, 7, 6, 9, 14, 12};
        int bricks = 5;
        int ladders = 1;

        System.out.println(furthestBuilding(heights, bricks, ladders));

        heights = new int[]{4, 12, 2, 7, 3, 18, 20, 3, 19};
        bricks = 10;
        ladders = 2;

        System.out.println(furthestBuilding(heights, bricks, ladders));
    }
}
